翻訳と辞書 Words near each other ・ Combined Scottish Universities by-election, 1945 ・ Combined Scottish Universities by-election, 1946 ・ Combined Security Transition Command – Afghanistan ・ Combined Services (Pakistan) cricket team ・ Combined Services cricket team ・ Combined Services Detailed Interrogation Centre ・ Combined Services Entertainment ・ Combined Services Polo Club ・ Combinatorial game theory ・ Combinatorial group theory ・ Combinatorial hierarchy ・ Combinatorial map ・ Combinatorial meta-analysis ・ Combinatorial method ・ Combinatorial method (linguistics) ・ Combinatorial number system ・ Combinatorial optimization ・ Combinatorial principles ・ Combinatorial proof ・ Combinatorial search ・ Combinatorial species ・ Combinatorial topology ・ Combinatoriality ・ Combinatorica ・ Combinatorics ・ Combinatorics and dynamical systems ・ Combinatorics and physics ・ Combinatorics on words ・ Combinatorics, Probability and Computing ・ Combinatory categorial grammar Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Combinatorial number system ： ウィキペディア英語版 Combinatorial number system In mathematics, and in particular in combinatorics, the combinatorial number system of degree ''k'' (for some positive integer ''k''), also referred to as combinadics, is a correspondence between natural numbers (taken to include 0) ''N'' and ''k''-combinations, represented as strictly decreasing sequences ''c''''k'' > ... > ''c''2 > ''c''1 ≥ 0. Since the latter are strings of numbers, one can view this as a kind of numeral system for representing ''N'', although the main utility is representing a ''k''-combination by ''N'' rather than the other way around. Distinct numbers correspond to distinct ''k''-combinations, and produce them in lexicographic order; moreover the numbers less than $\backslash tbinom\; nk$ correspond to all ''k''-combinations of }. The correspondence does not depend on the size ''n'' of the set that the ''k''-combinations are taken from, so it can be interpreted as a map from N to the ''k''-combinations taken from N; in this view the correspondence is a bijection. The number ''N'' corresponding to (''c''''k'',...,''c''2,''c''1) is given by :$N=\backslash binomk+\backslash cdots+\backslash binom2+\backslash binom1.$ The fact that a unique sequence so corresponds to any number ''N'' was observed by D.H. Lehmer.〔''Applied Combinatorial Mathematics'', Ed. E. F. Beckenbach (1964), pp.27−30.〕 Indeed a greedy algorithm finds the ''k''-combination corresponding to ''N'': take ''c''''k'' maximal with $\backslash tbinomk\backslash leq\; N$, then take ''c''''k'' − 1 maximal with $\backslash tbinom\backslash leq\; N\; -\; \backslash tbinomk$, and so forth. Finding the number ''N'', using the formula above, from the ''k''-combination (''c''''k'',...,''c''2,''c''1) is also known as "ranking", and the opposite operation (given by the greedy algorithm) as "unranking"; these operations are known by those names in most Computer algebra systems, and in computational mathematics.〔http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf〕〔http://www.sagemath.org/doc/reference/sage/combinat/subset.html〕 The originally used term "combinatorial representation of integers" is shortened to "combinatorial number system" by Knuth,〔.〕 who also gives a much older reference; the term "combinadic" is introduced by James McCaffrey (without reference to previous terminology or work). Unlike the factorial number system, the combinatorial number system of degree ''k'' is not a mixed radix system: the part $\backslash tbinomi$ of the number ''N'' represented by a "digit" ''c''''i'' is not obtained from it by simply multiplying by a place value. The main application of the combinatorial number system is that it allows rapid computation of the ''k''-combination that is at a given position in the lexicographic ordering, without having to explicitly list the ''k''-combinations preceding it; this allows for instance random generation of ''k''-combinations of a given set. Enumeration of ''k''-combinations has many applications, among which software testing, sampling, quality control, and the analysis of lottery games. == Ordering combinations == A ''k''-combination of a set ''S'' is a subset of ''S'' with ''k'' (distinct) elements. The main purpose of the combinatorial number system is to provide a representation, each by a single number, of all $\backslash tbinom\; nk$ possible ''k''-combinations of a set ''S'' of ''n'' elements. Choosing, for any ''n'', } as such a set, it can be arranged that the representation of a given ''k''-combination ''C'' is independent of the value of ''n'' (although ''n'' must of course be sufficiently large); in other words considering ''C'' as a subset of a larger set by increasing ''n'' will not change the number that represents ''C''. Thus for the combinatorial number system one just considers ''C'' as a ''k''-combination of the set N of all natural numbers, without explicitly mentioning ''n''. In order to ensure that the numbers representing the ''k''-combinations of } are less than those representing ''k''-combinations not contained in }, the ''k''-combinations must be ordered in such a way that their largest elements are compared first. The most natural ordering that has this property is lexicographic ordering of the ''decreasing'' sequence of their elements. So comparing the 5-combinations ''C'' =  and ''C''' = , one has that ''C'' comes before ''C''', since they have the same largest part 9, but the next largest part 6 of ''C'' is less than the next largest part 7 of ''C'''; the sequences compared lexicographically are (9,6,4,3,0) and (9,7,3,1,0). Another way to describe this ordering is view combinations as describing the ''k'' raised bits in the binary representation of a number, so that ''C'' =  describes the number :$2^+2^+\backslash cdots+2^$ (this associates distinct numbers to ''all'' finite sets of natural numbers); then comparison of ''k''-combinations can be done by comparing the associated binary numbers. In the example ''C'' and ''C''' correspond to numbers 10010110012 = 60110 and 10100010112 = 65110, which again shows that ''C'' comes before ''C'''. This number is not however the one one wants to represent the ''k''-combination with, since many binary numbers have a number of raised bits different from ''k''; one wants to find the relative position of ''C'' in the ordered list of (only) ''k''-combinations. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Combinatorial number system」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.